//
// Description: 496. 下一个更大元素 I
// Created by Loading on 2021/10/26.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
    vector<int> res;
    // 单调栈
    stack<int> s;
    // hash map存储右边第一个比其大的元素
    unordered_map<int, int> m;

    // 由于求右侧，所以采用逆序遍历
    for (int i = (int) nums2.size() - 1; i >= 0; --i) {
        // 当前元素大于栈顶元素，出栈，直到找到小于栈顶元素，即为结果
        while (!s.empty() && nums2[i] > s.top()) {
            s.pop();
        }
        // 栈空代表当前元素右侧没有比其更大的元素
        m[nums2[i]] = s.empty() ? -1 : s.top();
        s.emplace(nums2[i]);
    }

    for (auto &x : nums1) {
        res.emplace_back(m[x]);
    }

    return res;
}

int main() {
    vector<int> nums1 = {4, 1, 2};
    vector<int> nums2 = {1, 3, 4, 2};
    vector<int> res = nextGreaterElement(nums1, nums2);
    for (auto &x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}